package com.company.剑指offer每日刷题.专项版;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer II 010. 和为 k 的子数组
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

 * 示例 1 :
 *
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2
 * 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

 * 提示:
 *
 * 1 <= nums.length <= 2 * 104
 * -1000 <= nums[i] <= 1000
 * -107 <= k <= 107
 * */
public class SubarraySum {


    /**
     * 方法1：前缀和
     * 思路： 1.可以求出把 [n1,n2....,nn]的所有元素，进行累加，计算出每一项的前n项和，得到和的前缀和序列 [0,S1,S2....Sn]。
     *      2.  因为 Sj - Si = ni+1 + ni+2 + ni+3 + ...+ nj，所以我们就可以快速地求出来一个范围的子数组的和。
     *      3.这时，我们把每个Si 存起来，作为备选的起点，新计算出来的sj作为数组的终点。判断 sj - k = Si(Si可以是任意之前出现过的前缀和)
     *      如果存在这样的Si,就表示 从i+1到 j的这段子数组的和是等于 k的。也就是  Sj - Si = k，这样的Si出现的次数代表了和为k的子数组个数
     *      4.而上面这样的Si在已经产生的前缀和中出现了多次。这里为了优化避免通过遍历的方式去统计这些值的个数。我们可以直接用map，将这些前缀和
     *      出现过的次数统计起来。快速地找到它并且纳入结果之中。
     *
     * */
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int sum=0;
        int res = 0;
        //(0,1)表示，值为0的前缀和出现了1次。用于统计那些起点为0的目标子数组的个数
        map.put(0,1);
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            //在map中没有出现过的前缀和，默认为出现个数是 0
            res += map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0) +1);
        }
        return  res;
    }

    public static void main(String[] args) {
        SubarraySum obj = new SubarraySum();
        int i = obj.subarraySum(new int[]{1, 2, 3,3,-2,5}, 3);
        System.out.println(i);
    }
}
